#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define FOUND -1
#define NOTFOUND -3

typedef struct _Node{
    int Val;
    struct _Node *Left;
    struct _Node *Right;
} Node;

Node *buildSegmentTree(int *arr,int left,int right);
int findLeftMost(Node *root,int v);

int numOfUnplacedFruits(int* fruits, int fruitsSize, int* baskets, int basketsSize) {
    Node *root=buildSegmentTree(baskets,0,basketsSize-1);
    int ret=0;
    for( int i=0; i < fruitsSize; i++ ){
        if( findLeftMost(root,fruits[i]) == NOTFOUND )
            ret++;
    }
    return ret;
}



int max(int a,int b){
    return a>b?a:b;
}

Node *buildSegmentTree(int *arr,int left,int right){
    if( left == right ){
        Node *new=malloc(sizeof(Node));
        new->Val=arr[left];
        new->Left=new->Right=NULL;
        return new;
    }
    Node *root=malloc(sizeof(Node));
    root->Left=buildSegmentTree(arr,left,left+(right-left)/2);
    root->Right=buildSegmentTree(arr,left+(right-left)/2+1,right);
    root->Val=max(root->Left->Val,root->Right->Val);
    return root;
}
int findLeftMost(Node *root,int v){
    /*
    if( !root ){
        printf("Something wrong\n");
        return NOTFOUND;
    }*/
    if( root->Val < v )
        return NOTFOUND;
    int tmp;
    if( root->Left && root->Left->Val >= v ){
        tmp=findLeftMost(root->Left,v);
        root->Val=max(tmp,root->Right->Val);
    }
    else if( root->Right && root->Right->Val >= v ){
        tmp=findLeftMost(root->Right,v);
        root->Val=max(root->Left->Val,tmp);
    }
    else{
        root->Val=FOUND;
    }
    return root->Val;
}
int main(){
    int fruits[] = {4,2,5};
    int baskets[] = {3,5,4};
    printf("%d\n",numOfUnplacedFruits(fruits,sizeof(fruits)/sizeof(int),baskets,sizeof(baskets)/sizeof(int)));
    return 0;
}
